package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder

/**
https://leetcode.cn/problems/insert-into-a-binary-search-tree/

题型：二叉搜索树的遍历顺序

701. 二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

示例 1：
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]

示例 2：
输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]
 */
class leetcode_701 {
    @Test
    fun test_1() {
        val root = TreeNode(4)
        val n2 = TreeNode(2)
        val n7 = TreeNode(7)
        val n1 = TreeNode(1)
        val n3 = TreeNode(3)
        root.left = n2
        root.right = n7
        n2.left = n1
        n2.right = n3


        val result = insertIntoBST(root, 5)
        val actual = printLevelOrder(result)
        val expect: ArrayList<ArrayList<Int>> = arrayListOf(arrayListOf(4), arrayListOf(2, 7), arrayListOf(1, 3, 5))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val n40 = TreeNode(40)
        val n20 = TreeNode(20)
        val n60 = TreeNode(60)
        val n10 = TreeNode(10)
        val n30 = TreeNode(30)
        val n50 = TreeNode(50)
        val n70 = TreeNode(70)
        val root = n40
        root.left = n20
        root.right = n60
        n20.left = n10
        n20.right = n30
        n60.left = n50
        n60.right = n70


        val result = insertIntoBST(root, 25)
        val actual = printLevelOrder(result)
        val expect: ArrayList<ArrayList<Int>> = arrayListOf(arrayListOf(40), arrayListOf(20, 60), arrayListOf(10, 30, 50, 70), arrayListOf(25))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    fun insertIntoBST(root: TreeNode?, `val`: Int): TreeNode? {
        /*
        要点：
        1 插入的位置是叶子节点的位置。根据大小方向，找到这个节点为null，那么这就是要插入的位置。
        2 不用考虑用何种遍历方式，根据大小方向遍历。
        3 不用考虑重构二叉树
         */
        //  return insertIntoBST1(root,`val`)
        return insertIntoBST2(root, `val`)
    }

    fun insertIntoBST1(root: TreeNode?, `val`: Int): TreeNode? {
        // 递归
        // T - LogN
        // S - H
        // 终止条件：找到为null的节点
        if (null == root) {
            return TreeNode(`val`)
        }


        // 往左
        if (root.`val` > `val`) {
            root.left = insertIntoBST1(root.left, `val`) // 新的左孩子
        }

        // 往右
        if (root.`val` < `val`) {
            root.right = insertIntoBST1(root.right, `val`) // 新的右孩子
        }
        return root
    }

    fun insertIntoBST2(root: TreeNode?, `val`: Int): TreeNode? {
        // 迭代
        // T - LogN
        // S - H
        if (null == root) {
            // TODO:root 为null，val 将作为根节点
            return TreeNode(`val`)
        }

        var current: TreeNode? = root
        var pre: TreeNode? = null
        // 终止条件：找到为null的节点，该节点的父节点Pre
        while (current != null) {
            // TODO:pre 设置放在这里才可以
            pre = current
            if (current.`val` > `val`) {
                current = current.left
            } else { // current.`val` < `val`
                current = current.right
            }
        }
        pre?.let {
            if (`val` < it.`val`) { // 新的左孩子
                it.left = TreeNode(`val`)
            } else {// `val` > it.`val`) 新的右孩子
                it.right = TreeNode(`val`)
            }
        }

        return root
    }
}